Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:

Did you use extra space?

A straight forward solution using O(mn) space is probably a bad idea.

A simple improvement uses O(m + n) space, but still not the best solution.

Could you devise a constant space solution?

Solution:

  1. public class Solution {
  2.   public void setZeroes(int[][] matrix) {
  3.     int n = matrix.length;
  4.     int m = matrix[0].length;
  6.     // Check if we need to set zeros for first row and column
  7.     boolean cleanFirstRow = false;
  8.     boolean cleanFirstCol = false;
  10.     for (int j = 0; j < m; j++) {
  11.       if (matrix[0][j] == 0) {
  12.         cleanFirstRow = true;
  13.         break;
  14.       }
  15.     }
  17.     for (int i = 0; i < n; i++) {
  18.       if (matrix[i][0] == 0) {
  19.         cleanFirstCol = true;
  20.         break;
  21.       }
  22.     }
  24.     // Use first row and first column to save the flags
  25.     for (int i = 1; i < n; i++) {
  26.       for (int j = 1; j < m; j++) {
  27.         if (matrix[i][j] == 0) {
  28.           matrix[0][j] = 0;
  29.           matrix[i][0] = 0;
  30.         }
  31.       }
  32.     }
  34.     // Based on the flags set other cells
  35.     for (int i = 1; i < n; i++) {
  36.       for (int j = 1; j < m; j++) {
  37.         if (matrix[0][j] == 0 || matrix[i][0] == 0) {
  38.           matrix[i][j] = 0;
  39.         }
  40.       }
  41.     }
  43.     // At last set the first row and column
  44.     if (cleanFirstRow) {
  45.       for (int j = 0; j < m; j++) {
  46.         matrix[0][j] = 0;
  47.       }
  48.     }
  50.     if (cleanFirstCol) {
  51.       for (int i = 0; i < n; i++) {
  52.         matrix[i][0] = 0;
  53.       }
  54.     }
  55.   }
  56. }